class Solution(object):
    def mincostTickets(self, days, costs):
        now = [-1] * 30
        now[0] = costs[0]
        now[6] = costs[1]
        now[29] = costs[2]
        n = len(days)
        for i in range(1, n):
            diff = days[i] - days[i - 1]
            next_st = [-1] * 30
            for k in range(30):
                if now[k] >= 0:
                    if k >= diff:
                        next_st[k - diff] = min(next_st[k - diff], now[k]) if next_st[k - diff] >= 0 else now[k]
                    else:
                        next_st[0] = min(next_st[0], now[k] + costs[0]) if next_st[0] >= 0 else now[k] + costs[0]
                        next_st[6] = min(next_st[6], now[k] + costs[1]) if next_st[6] >= 0 else now[k] + costs[1]
                        next_st[29] = min(next_st[29], now[k] + costs[2]) if next_st[29] >= 0 else now[k] + costs[2]
            now = next_st
        min_value = float('inf')
        for k in range(30):
            if now[k] >= 0:
                min_value = min(min_value, now[k])
        return min_value


data = Solution()
days = [1, 4, 6, 7, 8, 20]
costs = [2, 7, 15]
print(data.mincostTickets(days, costs))
